/**
 * https://leetcode.cn/problems/total-cost-to-hire-k-workers/submissions/590090247/
 * 2462.雇佣k位工人的总代价
 * medium 2024.12.29
 * 优先队列
 */

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        auto cmp = [](const pair<int, int> & a, const pair<int, int> & b) {
           if(a.first!=b.first)
                return a.first>b.first;
            return a.second>b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        int l=0;
        int r=costs.size()-1;
        while(l<candidates){
            q.emplace(costs[l],l);
            l++;
        }
        while(r>=l&&candidates--){
            q.emplace(costs[r],r);
            r--;
        }
        long long ans=0;
        while(k--){
            auto [val,d]=q.top();
            ans+=val;
            q.pop();
            if(d<l&&l<=r){
                q.emplace(costs[l],l);
                l++;
            }else if(d>r&&r>=l){
                q.emplace(costs[r],r);
                r--;
            }
        }
        return ans;
    }
};